package niuke;

/**
 * description:
 * author:张腾
 * date:2021-06-29
 */

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 给出一组可能包含重复项的数字，返回该组数字的所有排列
 */
public class NC42 {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    ArrayList<Integer> path = new ArrayList<>();
    boolean[] visited;
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        if (num.length==0 || num==null) return new ArrayList<>();
        visited = new boolean[num.length];
        Arrays.sort(num);
        dfs(num,num.length);
        return res;
    }

    private void dfs(int[] num,int len){
        if (path.size()==len) res.add(new ArrayList<>(path));

        for (int i = 0; i < len; i++) {
            if (i>0 && num[i]==num[i-1] && !visited[i-1]) continue;
            if (!visited[i]){
                path.add(num[i]);
                visited[i] = true;
                dfs(num,len);
                visited[i] = false;
                path.remove(path.size()-1);
            }
        }
    }
}
